import math


# 优化
# class Solution(object):
#     def subarrayGCD(self, nums, k):
#         n = len(nums)
#         ans = 0
#         for i in range(n):
#             if nums[i] % k != 0:
#                 continue
#             else:
#                 if nums[i] == k:
#                     ans += 1
#                 for j in range(i + 1, n):
#                     if math.gcd(nums[i], nums[j]) == k:
#                         ans += 1
#                     else:
#                         break
#         return ans

class Solution(object):
    def subarrayGCD(self, nums, k):
        a = []
        ans = 0
        i0 = -1
        for index, num in enumerate(nums):
            if num % k != 0:
                a = []
                i0 = index
                continue
            a.append([num, index])
            j = 0
            for p in a:
                p[0] = math.gcd(p[0], num)
                if p[0] != a[j][0]:
                    j += 1
                    a[j] = [p[0], p[1]]
                else:
                    a[j][1] = p[1]
            del a[j + 1:]
            if a[0][0] == k:
                ans += a[0][1] - i0
        return ans


data = Solution()
nums = [9, 3, 1, 2, 6, 3]
k = 3
print(data.subarrayGCD(nums, k))
